package algorithm;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author MaGuangQi
 * @description 滑动窗口 239题
 *  https://leetcode-cn.com/problems/sliding-window-maximum/
 *  给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
 *
 * 返回滑动窗口中的最大值。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/sliding-window-maximum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2020-06-18 22:32
 **/
public class SlideWindow {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        if (n<k) {
            return nums;
        }
        //返回的结果
        int[] result = new int[n - k + 1];
        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            //step1 头部出队,清理超出范围的
            if (!deque.isEmpty() && deque.getFirst() < (i - k + 1)) {
                deque.removeFirst();
            }
            //step2 清除尾部,清除尾部的值小于当前值的,因为只要当前值在,队列左边的就没有出头之日
            while (!deque.isEmpty() && nums[i] >= nums[deque.getLast()]) {
                deque.removeLast();
            }
            //step3 尾部入队
            deque.addLast(i);
            //step4 返回头部
            if (i >= k - 1) {
                //因为上面已经限制了i>=k-1,因此第一次进入的时候是i=k-1
                //此时i-k+1等于0,i每次加1,也就是result[0] result[1]...
                result[i - k + 1] = nums[deque.getFirst()];
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums={1,3,-1,-3,5,3,6,7};
        int k = 3;
        for (int i : maxSlidingWindow(nums, k)) {
            System.out.println("值是"+i);
        }
    }
}
